package com.leetcode.周赛.第231场;

/**
 * @author: xiaomi
 * @date: 2021/3/7
 * @description: 5700. 使所有区间的异或结果为零
 * https://leetcode-cn.com/contest/weekly-contest-231/problems/make-the-xor-of-all-segments-equal-to-zero/
 */
public class C_5700_使所有区间的异或结果为零 {

    static C_5700_使所有区间的异或结果为零 action = new C_5700_使所有区间的异或结果为零();

    public static void main(String[] args) {
//        test1();
//        test2();
        test3();
    }

    public static void test1() {
        // 3
        int[] nums = new int[]{1, 2, 0, 3, 0};
        int k = 1;
        int res = action.minChanges(nums, k);
        System.out.println("res = " + res);
        //
    }

    public static void test2() {
        // 3
        int[] nums = new int[]{3, 4, 5, 2, 1, 7, 3, 4, 7};
        int k = 3;
        int res = action.minChanges(nums, k);
        System.out.println("res = " + res);
    }

    public static void test3() {
        // 3
        int[] nums = new int[]{26, 19, 19, 28, 13, 14, 6, 25, 28, 19, 0, 15, 25, 11};
        int k = 3;
        int res = action.minChanges(nums, k);
        System.out.println("res = " + res);
    }

    /**
     * 我只能暂且用贪心的算法 + 暴力 来求
     * 有BUG 存在 0 19 19 这种情况！无法找规律完结。
     * @param nums
     * @param k
     * @return
     */
    public int minChanges(int[] nums, int k) {
        int len = nums.length;
        int xor = nums[0];
        for (int i = 1; i < k; i++) {
            xor ^= nums[i];
        }
        int min = Integer.MAX_VALUE;
        int[] copyArr = new int[k];
        System.arraycopy(nums, 0, copyArr, 0, k);
        for (int i = 0; i < k; i++) {
            int leftCount = 0;
            int oldV = copyArr[i];
            xor ^= copyArr[i];
            if (oldV != xor) {
                copyArr[i] = xor;
                leftCount++;
            }

            min = Math.min(min, getMin(copyArr, nums, k, len) + leftCount);
            //还原操作
            xor ^= oldV;
            copyArr[i] = oldV;
        }
        return min;
    }

    private int getMin(int[] copyArr, int[] nums, int k, int len) {
        int count = 0;
        int ci = 0;
        for (int i = k; i < len; i++) {
            if (copyArr[ci] != nums[i]) {
                count++;
            }
            ci++;
            if (ci == k) {
                ci = 0;
            }
        }
        return count;
    }
}
